package com.yt.ds.chapter2;

import com.yt.ds.util.SortUtil;

/**
 * @Author: lzf
 * @Date: 2020/7/11 15:49
 * @Description: 希尔排序  (插入排序的改进版)
 */
public class ShellSort implements Sort {
    @Override
    public Comparable[] sort(Comparable[] array) {
        int h = 1;
        while (h < array.length / 3) {
            h = h * 3 + 1;
        }
        while (h >= 1) {
            System.out.println("h:" + h);
            for (int i = h; i < array.length; i++) {
                for (int j = i; j >= h && array[j].compareTo(array[j - h]) < 0; j -= h) {
                    SortUtil.exch(array, j, j - h);
                }
            }
            h = h / 3;
        }
        return array;
    }
}
